Welcome! This is ratel's Blog.

개발 스터디
- JavaScript
- algorithm
개발일지
Home

Contact

Copyright © 2024 | Yankos

Home > 개발 스터디 > algorithm

Now Loading ...

algorithm

test
test
개발 스터디 · 2025-06-16
dynamic programming
동적 계획법(Dynamic Programming) WHAT IS? 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 컨셉! 수열의 점화식 느낌 유남생? aka ‘기억하며 풀기’ WHY USE? 사실 DP는 일반적인 재귀법과 매우 유사함. 하지만 그 효율성은 말도 못하게 더 높다. 일반적인 재귀법은 보통 O(n^2)의 시간 복잡도를 나타내는 반면 DP는 O(f(n))의 시간 복잡도를 보인다. 위 그림처럼 재귀법을 사용한다면 불필요하게 한번 구했던 값 (=함수 호출 횟수)을 한번 더 구해야함. 이때 한번 구한 작은 문제의 결과 를 저장했다가 재사용 하면 굉장히 효율적이게 되겠죵? 이것이 바로 DP의 핵심 개념입니다! WHAT CONDITIONS? DP를 사용하기 위해서는 아래 2조건을 만족해야 합니다. 겹치는 부분 문제 (Overlapping Subproblems) DP는 기본적으로 문제를 나누고 그 문제의 결과 값을 재활용해서 전체 답을 구한다. 그래서 동일한 작은 문제들이 반복하여 나타나는 경우에 사용이 가능하다. 즉, DP는 부분 문제의 결과를 저장하여 재 계산하지 않을 수 있어야 하는데, 해당 부분 문제가 반복적으로 나타나지 않는다면 재사용이 불가능하니 부분 문제가 중복되지 않는 경우에는 사용할 수 없다. 최적 부분 구조 (Optimal Substructure) 부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우를 의미한다. 만약, A - B까지의 가장 짧은 경로를 찾고자 하는 경우를 예시로 할 때, 중간에 X가 있을 때, A - X / X - B가 많은 경로 중 가장 짧은 경로라면 전체 최적 경로도 A - X - B가 정답이 된다. HOW USE? 아래 단계를 거쳐 문제를 해결할 수 있습니다. DP로 풀 수 있는 문제인지 확인 문제의 변수 파악 변수 간 관계식 만들기(점화식) 메모하기(memoization or tabulation) 기저 상태 파악하기 구현하기 1. DP로 풀 수 있는 문제인지 확인 현재 직면한 문제가 작은 문제들로 이루어진 하나의 함수로 표현될 수 있는지를 판단 보통 특정 데이터 내 최대화 / 최소화 계산을 하거나 특정 조건 내 데이터를 세야 한다거나 확률 등의 계산의 경우 DP로 풀 수 있는 경우가 많다. 2. 문제의 변수 파악 문제 내 변수의 개수를 알아내야 한다. ( = state를 결정한다.) 예를 들어, 피보나치 수열에서는 n번째 숫자를 구하는 것이므로 n이 변수가 된다. 그 변수가 얼마이냐에 따라 결과값이 다르지만 그 결과를 재사용하고 있다. 3. 변수 간 관계식(점화식) 만들기 변수들에 의해 결과 값이 달라지지만 동일한 변수값인 경우 결과는 동일하므로 우리는 이를 관계식으로 만들어 낼 수 있고 그 관계식을 점화식이라고 한다! 예를 들어 피보나치 수열에서는 f(n) = f(n-1) + f(n-2) 4. 메모하기 변수 간 관계식까지 정상적으로 생성되었다면 변수의 값에 따른 결과를 저장 보통 배열을 쓰며 변수의 개수에 따라 배열의 차원이 1~3차원 등 다양할 수 있다. 5. 기저 상태 파악하기 가장 작은 문제의 상태를 알아야 한다. 피보나치 수열을 예시로 들면, f(0) = 0, f(1) = 1과 같은 방식 해당 기저 문제에 대해 파악 후 미리 배열 등에 저장해두면 된다. 6. 구현하기 2가지 방식으로 구현 가능함. Bottom-Up (Tabulation 방식) - 반복문 사용 아래에서 부터 계산을 수행 하고 누적시켜서 전체 큰 문제를 해결하는 방식 dp[0]부터 시작하여 반복문을 통해 점화식으로 결과를 내서 dp[n]까지 그 값을 전이시켜 재활용하는 방식 메모하기 부분에서 Memoization이라고 했는데 Bottom-up일 때는 Tabulation이라고 부른다. Top-Down (Memoization 방식) - 재귀 사용 dp[0]의 기저 상태에서 출발하는 대신 dp[n]의 값을 찾기 위해 위에서 부터 바로 호출을 시작하여 dp[0]의 상태까지 내려간 다음 해당 결과 값을 재귀를 통해 전이시켜 재활용하는 방식 packge com.test; public class Fibonacci{ // DP 를 사용 시 작은 문제의 결과값을 저장하는 배열 // Top-down, Bottom-up 별개로 생성하였음(큰 의미는 없음) static int[] topDown_memo; static int[] bottomup_table; public static void main(String[] args){ int n = 30; topDown_memo = new int[n+1]; bottomup_table = new int[n+1]; long startTime = System.currentTimeMillis(); System.out.println(naiveRecursion(n)); long endTime = System.currentTimeMillis(); System.out.println("일반 재귀 소요 시간 : " + (endTime - startTime)); System.out.println(); startTime = System.currentTimeMillis(); System.out.println(topDown(n)); endTime = System.currentTimeMillis(); System.out.println("Top-Down DP 소요 시간 : " + (endTime - startTime)); System.out.println(); startTime = System.currentTimeMillis(); System.out.println(bottomUp(n)); endTime = System.currentTimeMillis(); System.out.println("Bottom-Up DP 소요 시간 : " + (endTime - startTime)); } // 단순 재귀를 통해 Fibonacci를 구하는 경우 // 동일한 계산을 반복하여 비효율적으로 처리가 수행됨 public static int naiveRecursion(int n){ if(n <= 1){ return n; } return naiveRecursion(n-1) + naiveRecursion(n-2); } // DP Top-Down을 사용해 Fibonacci를 구하는 경우 public static int topDown(int n){ // 기저 상태 도달 시, 0, 1로 초기화 if(n < 2) return topDown_memo[n] = n; // 메모에 계산된 값이 있으면 바로 반환! if(topDown_memo[n] > 0) return topDown_memo[n]; // 재귀를 사용하고 있음! topDown_memo[n] = topDown(n-1) + topDown(n-2); return topDown_memo[n]; } // DP Bottom-Up을 사용해 Fibonacci를 구하는 경우 public static int bottomUp(int n){ // 기저 상태의 경우 사전에 미리 저장 bottomup_table[0] = 0; bottomup_table[1] = 1; // 반복문을 사용하고 있음! for(int i=2; i<=n; i++){ // Table을 채워나감! bottomup_table[i] = bottomup_table[i-1] + bottomup_table[i-2]; } return bottomup_table[n]; } } /* 결과 832040 일반 재귀 소요 시간 : 9 832040 Top-Down DP 소요 시간 : 0 832040 Bottom-Up DP 소요 시간 : 0 */
개발 스터디 · 2025-06-16

Touch background to close